Ulaanbaatar trước đó đã từng mang nhiều tên gọi trong lịch sử. Từ 1639 đến 1706, thành phố được gọi là Urga (tiếng Mông Cổ: Өргөө, Örgöö, "Cư trú"), và từ năm 1706 đến 1911 với tên gọi Kuren (Хүрээ, Xüree, "Lều"), Da-Kuren (Даа Хүрээ, Daa Xüree, từ tiếng Trung: 大, đại, chuyển tự của tiếng Mông Cổ: Их Хүрээ, Ix Xüree, "Trại Lớn"), hoặc Kulun (tiếng Trung: 庫倫 Khố Luân, chuyển tự của Xüree). Thành phố được gọi là Bogdiin Khuree (Богдийн Хүрээ, Bogdiĭn Xüree, "Lều Thánh" hay "Tu viện vĩ đại của khả hãn") trong bài dân ca "Tôn kính Bogdiin Khuree".

Sau khi Mông Cổ độc lập vào năm 1911, cả chính quyền thế tục và cung điện của Khan/Hãn Bogd đều đổi tên thành phố thành Niĭslel Xüree (Нийслэл Хүрээ, "Lều Thủ đô").

Năm 1924, thành phố trở thành thủ đô của nước Cộng hòa Nhân dân Mông Cổ mới được thành lập, tên của thành phố được đổi thành Ulaanbaatar (Улаанбаатар, Ulaanbaatar, nghĩa là "Anh hùng Đỏ") để tỏ lòng kính trọng đối với anh hùng dân tộc Mông Cổ Damdin Sükhbaatar, người đã kề vai sát cánh với Hồng quân Liên Xô giải phóng Mông Cổ khỏi sự chiếm đóng của Trung Quốc và chống lại quân đội xâm lược của Roman von Ungern-Sternberg, tượng của ông nay vẫn được đặt tại quảng trường trung tâm thủ đô. Trong phiên họp của Đại dân tộc Khuraldaan đầu tiên của Mông Cổ năm 1924, đa số đại biểu bày tỏ mong muốn đổi tên thành phố thủ đô thành Baatar Khot ("Thành phố anh hùng"). Tuy nhiên, dưới áp lực của Turar Ryskulov, một nhà hoạt động Liên Xô của Quốc tế Cộng sản, thành phố được đặt tên là Ulaanbaatar Khot ("Thành phố của anh hùng đỏ").

Ở châu Âu và Bắc Mỹ, Ulaanbaatar tiếp tục được gọi chung là Urga hoặc Khure cho đến năm 1924. Do ảnh hưởng lâu dài của Liên Xô tại Mông Cổ, tên gọi Ulan Bator chuyển tự từ tiếng Nga (tiếng Nga: Улан-Батор, Ulan-Bator) đã trở thành tên gọi thông dụng của thành phố trong nhiều ngôn ngữ. Cách viết tên thành phố trong chữ cái tiếng Nga khác với trong chữ cái tiếng Mông Cổ là do liên quan đến các vấn đề về định nghĩa phát âm, và chữ cái Kirin mới chỉ được giới thiệu tại Mông Cổ 17 năm sau khi mước này giành được độc lập. Với người Mông Cổ, thành phố có biệt danh là Aziĭn Cagaan Dagina (Азийн Цагаан Дагина, "Nàng tiên Trắng [Dakini của châu Á") vào cuối thế kỷ 20. Tại Mông Cổ ngày nay, thành phố đôi khi được gọi một cách châm biếm là Utaanbaatar (Утаанбаатар, "Anh hùng Sương khói") do có sương mù dày đặc vào mùa đông.